Conventionally, a recording device is known (see, for example, Patent Literature 1) which includes memory means for storing multiple folders and multiple pieces of folder attribute information representing the attribute of each of the multiple folders, and means for obtaining main data like music data and sub data representing the attribute of the song title or the like of music represented by the main data. This recording device generates a new folder when there is no folder attribute information representing the same attribute as the attribute represented by the obtained sub data, and records the main data in the newly generated folder.